package BinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;

public class TreeNode implements InterFace{

    private TreeNode left;
    private int val;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }


    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

    @Override
    public int size(TreeNode root) {
        //使用递归遍历来获取节点个数
        return recursionSize(root);
    }
    private int  recursionSize(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = recursionSize(node.left);
        int r = recursionSize(node.right);
        return l + r + 1;
    }

    public int recursion(TreeNode node){
        if (node == null) {
            return 0;
        }
        if (node.right == null && node.left == null) {
            return 1;
        }

        int i = recursion(node.left);
        int j = recursion(node.right);
        return i + j;

    }

    public int getCount(TreeNode node, int k) {
        if (node == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }

        int i = getCount(node.left,k-1);
        int j = getCount(node.right,k- 1);

        return i + j;
    }

    public int getHigh(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int r = getHeight(node.left);
        int l = getHeight(node.right);
        return  Math.max(r, l) + 1;
    }



    @Override
    public int getLeveNode(TreeNode root) {
        //层序遍历节点，寻找没有左右孩子的节点
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.right == null && poll.left == null){
                count++;
            }
            if (poll.left != null ) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return count;
    }

    @Override
    public int getLeveNodeCount(TreeNode root,int k) {
        //层序遍历，得到每一层的个数，然后放到数组中
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        ArrayList<Integer> arrayList = new ArrayList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();
            arrayList.add(size);
            for (int i = 0; i < size ; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null ) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }

        }
        if ( k >= 1 && k - 1 <= arrayList.size() ) {
            return arrayList.get(k - 1);
        }else {
            return 0;
        }

    }

    @Override
    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = getHeight(node.left);
        int r = getHeight(node.right);

        return Math.max(l,r) + 1;
    }
    public TreeNode finalVal(TreeNode node,int val) {
        if (node == null) {
            return null;
        }
        if (node.val == val) {
            return node;
        }

        TreeNode l = finalVal(node.left,val);
        TreeNode r = finalVal(node.right,val);

        return l != null ? l : r;

    }

    @Override
    public TreeNode find(TreeNode root, int val) {
        return recursionFind(root,val);
    }
    private TreeNode recursionFind(TreeNode node,int val) {
        if (node == null) {
            return null;
        }
        if (node.val == val) {
            return node;
        }
        TreeNode last1 = recursionFind(node.left,val);
        TreeNode last2 = recursionFind(node.right,val);
        return (last1 != null ? last1 : last2);
    }

    @Override
    public void leveOrder(TreeNode root,Accept accept) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while ( !queue.isEmpty() ){

            int size = queue.size();
            for (int i = 0; i< size ; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                accept.accept(poll.val);
            }
            System.out.println();
        }

    }

    @Override
    public boolean isCompleteTree(TreeNode root) {
        //使用层序遍历，假如当前节点的左孩子为null而右孩子不为null,则不是完全二叉树。
        //或者
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sign = 0;
        while (!queue.isEmpty()) {

            TreeNode poll = queue.poll();

            if (poll.left != null || poll.right != null){
                if (sign == 1) {
                    return false;
                }
            }

            if (poll.left == null || poll.right == null) {
                sign = 1;
            }

            if (poll.left == null && poll.right != null) {
                return false;
            }

            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return true;
    }

    @Override
    public String toString() {
        return "TreeNode:" +
                " val=" + val ;
    }

    //判断两颗树是否相同
    public boolean isSame1(TreeNode s1, TreeNode s2) {
        if (s1 == null && s2 == null) {
            return true;
        }

        if (s1 == null || s2 == null) {
            return false;
        }
        if (s1.val != s2.val) {
            return false;
        }

        return isSame1(s1.left ,s2.left) && isSame1(s1.right ,s2.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        if(root == null) {
            return false;
        }
        if(isSame(root,subRoot)) {
            return true;
        }
        if(isSame(root.left , subRoot)) {
            return true;
        }
        if(isSame(root.right,subRoot)) {
            return true;
        }
        return false;

    }
    public boolean isSame(TreeNode r, TreeNode s) {

        if(r != null && s == null || s != null && r == null) {
            return false;
        }
        if(r == null) {
            return true;
        }
        if( r.val != s.val) {
            return false;
        }
        return isSame(r.left , s.left ) && isSame(r.right , s.right);
    }

}
